#ifndef HEAD_H
#define HEAD_H
#include<iostream>
using namespace std;

struct node{
    node* nx;
    int data;
};

class arraylist{
private:
    node*ahead;
    node*atail;

    node*bhead;
    node*btail;

public:
    arraylist();
    ~arraylist();
    void init_alist();
    void init_blist();
    void showlist(node *head);
    void mergelist();
    void inverselist();
    void destroylist(node*head);
};


arraylist::arraylist(){
    init_alist();
    init_blist();
    showlist(ahead);
    showlist(bhead);
    mergelist();
    inverselist();
}
arraylist::~arraylist(){
    destroylist(ahead);
    destroylist(bhead);
    atail=btail=NULL;
//    node*p;
//    while(ahead!=NULL){
//        p=ahead;
//        ahead=ahead->nx;
//        delete p;
//    }
//    while(bhead!=NULL){
//        p=bhead;
//        bhead=bhead->nx;
//        delete p;
//    }
//    ahead=bhead=atail=btail=NULL;
}
void arraylist::init_alist(){
    int i=0;
    node*p=ahead=new node;
    while (i<5) {
        p->nx=new node;
        p=p->nx;
       atail=p;
        p->data=2*i;
        i++;
    }
    atail->nx=NULL;
}
void arraylist::init_blist(){
    int i=0;
    node*p=bhead=new node;
    while (i<5) {
        btail=p=p->nx=new node;
        p->data=2*i+1;
        i++;
    }
    btail->nx=NULL;
}
void arraylist::showlist(node *head){
    node*p=head;
    cout<<endl;
    while(p->nx!=NULL){
        p=p->nx;
        cout<<p->data<<"\t";
    }
}

void arraylist::mergelist(){
    node* newhead;
    node*na,*nb,*nc;
    na=ahead->nx;
    nb=bhead->nx;
    newhead=nc=ahead;

    while(na&&nb){
        if(na->data<=nb->data){
            nc->nx=na;
            nc=na;
            na=na->nx;
        }
        else{
            nc->nx=nb;
            nc=nb;
            nb=nb->nx;
        }
    }
    //若有a,b有剩余，插入剩余部分
    if(nc->nx=na){
        nc->nx=na;
    }
    else{
        nc->nx=nb;
    }
    delete bhead;
//    node*a;
//    node*b=bhead;
//    node*p;

//    while(b->nx!=NULL){
//        b=b->nx;
//        a=ahead;
//        while (a->nx!=NULL) {
//            a=a->nx;
//            if(((a->nx->data)>(b->data))&&((a->data)<(b->data))){
//                p=a->nx;
//                a->nx=b;
//                b->nx=p;
//                break;
//            }
//        }
//    }
//    showlist(ahead);
//    destroylist(bhead);
}
void arraylist::destroylist(node *head){
        node*p;
        while(head!=NULL){
            p=head;
            head=head->nx;
            delete p;
        }
        head=NULL;
}

void arraylist::inverselist(){
    node*p=ahead->nx->nx;
    ahead->nx->nx=NULL;
    node*q=NULL;
    node*currenthead=ahead->nx;
    while(p!=NULL){
        q=p->nx;
        p->nx=ahead->nx;
        ahead->nx=p;
        p=q;
    }

    cout<<endl<<"the final result is: ";
    showlist(ahead);
}

#endif // HEAD_H
